﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Xml;

namespace eu.h8me.Parsing.ParserLib {

    /// <summary>
    /// Helper class used to carry a chain of symbols describing a production for a non-terminal.
    /// </summary>
    public sealed class Production : IEnumerable<Symbol> {

        /// <summary>
        /// Reduction event callback type called when a production is reduced. When a reduction path is not to be taken, the
        /// event may raise a FailReductionException, which causes the parser to ignore this reduction path.
        /// </summary>
        /// <param name="state">Current parse state on executing the reduction.</param>
        /// <param name="symbols">Tokens that are to be reduced.</param>
        /// <returns>Value that is to be assigned to the non-terminal token that was reduced.</returns>
        public delegate object ReduceEventType(ParseState state, Token[] symbols);

        // Data.
        private readonly Grammar _Grammar;
        private readonly List<Symbol> _Symbols;
        private object _Tag;
        private int? _RulePrecedence;
        private int? _MergePrecedence;
        private bool _Finished;
        private event ReduceEventType _ReduceEvent;

        /// <summary>
        /// Initialize a new, empty production that is bound to the respective grammar.
        /// </summary>
        /// <param name="gram">Grammar to bind the production to.</param>
        internal Production(Grammar gram) {
            // Create a zero-element production with no symbols.
            _Grammar = gram;
            _Symbols = new List<Symbol>();
        }

        /// <summary>
        /// Initialize a new production which carries one symbol (has length 1).
        /// </summary>
        /// <param name="symb">The symbol to insert into the production.</param>
        internal Production(Symbol symb) {
            // Create a one-element production with the specified symbol.
            _Grammar = symb.Grammar;
            _Symbols = new List<Symbol>() { symb };
        }

        /// <summary>
        /// Create a new production which is a copy of the passed production symbol list, but is independent of it.
        /// </summary>
        /// <param name="prod">Production to copy.</param>
        internal Production(Production prod) {
            // Copy the production as a new list.
            _Grammar = prod._Grammar;
            _Symbols = new List<Symbol>(prod._Symbols);
        }

        /// <summary>
        /// Fetch the grammar the current production is bound to.
        /// </summary>
        public Grammar Grammar {
            get {
                // Return grammar.
                return _Grammar;
            }
        }

        /// <summary>
        /// Access the tag that is bound to the current production. A tag may only be assigned to a production after the
        /// production has been finished (i.e., has been added to a non-terminal), and may not be reassigned after the grammar
        /// has been finished.
        /// </summary>
        public object Tag {
            get {
                // Return production tag.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to get tag when not finished");
                return _Tag;
            }
            set {
                // Check conditions.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to attach tag when not finished");
                else if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to set production tag after grammar is finished");

                // Set up tag.
                _Tag = value;
            }
        }

        /// <summary>
        /// Assign a specific rule precedence to a production. The default rule precedence for a production is taken from the
        /// symbol precedence of the right-most terminal that has a precedence set up, and decides whether to shift or reduce
        /// when a conflict is found and the precedence of the lookahead symbol and the production are not equivalent. A rule
        /// precedence may only be assigned after the production has been finished (i.e., added to a non-terminal), and may
        /// not be reassigned after the grammar has been finished.
        /// </summary>
        public int RulePrecedence {
            get {
                // Check preconditions.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to access rule precedence before finish");
                else if( _RulePrecedence.HasValue )
                    return _RulePrecedence.Value;

                // No direct precedence set up for rule; use precedence of right-most terminal.
                foreach( Symbol symb in _Symbols.Reverse<Symbol>() )
                    if( symb.IsTerminal && symb.HasSymbolPrecedence )
                        return symb.SymbolPrecedence;

                // No precedence set up, fail.
                throw new InvalidOperationException("Trying to get rule precedence on rule that has none set up");
            }
            set {
                // Store precedence.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to attach precedence when not finished");
                else if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to set production precedence after grammar is finished");
                _RulePrecedence = value;
            }
        }

        /// <summary>
        /// Check whether the current rule has a rule precedence set up.
        /// </summary>
        public bool HasRulePrecedence {
            get {
                // Check whether rule precedence is set up.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to test for rule precedence when not finished");
                else if( _RulePrecedence.HasValue )
                    return true;

                // Check for terminal.
                foreach( Symbol symb in _Symbols.Reverse<Symbol>() )
                    if( symb.IsTerminal && symb.HasSymbolPrecedence )
                        return true;

                // No terminal has precedence set up, and no explicit precedence, so none set up.
                return false;
            }
        }

        /// <summary>
        /// Assign or fetch the merge precedence that a particular production has assigned. When two different reduction paths
        /// join on a non-terminal and state, the two paths are merged to be one new path, and a merge callback on the reducing
        /// symbol is called (see Symbol). When different merge precedences have been set up for the two merging reduction paths,
        /// the one with the higher merge precedence is taken automatically without callback. Merge precedence may only be assigned
        /// after the production has been finished (i.e., added to a non-terminal), and may not be reassigned after the grammar
        /// has been finished.
        /// </summary>
        public int MergePrecedence {
            get {
                // Check whether precedence is set up.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to access rule precedence before finish");
                else if( !_MergePrecedence.HasValue )
                    throw new InvalidOperationException("No merge precedence set up");
                return _MergePrecedence.Value;
            }
            set {
                // Store precedence.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to set up merge precedence when not finished");
                else if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to set up merge precedence after grammar is finished");
                _MergePrecedence = value;
            }
        }

        /// <summary>
        /// Check whether a merge precedence has been set up for the rule.
        /// </summary>
        public bool HasMergePrecedence {
            get {
                // Return state.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to access rule content before finish");
                return _MergePrecedence.HasValue;
            }
        }

        /// <summary>
        /// Check whether the production is finished (i.e., added to a non-terminal).
        /// </summary>
        public bool IsFinished {
            get {
                // Return finished state.
                return _Finished;
            }
        }

        /// <summary>
        /// Check whether the production is empty (i.e., is an epsilon-production).
        /// </summary>
        public bool IsEmpty {
            get {
                // Check whether production is empty.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to access rule content before finish");
                return _Symbols.Count == 0;
            }
        }

        /// <summary>
        /// Attach or detach a reduce event from a finished production. Reduce events are called when the parser encounters a
        /// reduction possibility using this production. Reduce events may only be bound when the production has been finished,
        /// and may not be altered after the grammar has been finished.
        /// </summary>
        public event ReduceEventType ReduceEvent {
            add {
                // Attach an event if finished.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to attach reduce event after grammar finish");
                else if( !_Finished )
                    throw new InvalidOperationException("Trying to attach event when not finished");
                else if( value == null )
                    throw new ArgumentNullException("Illegal reduce event to add, is NULL");
                _ReduceEvent += value;
            }
            remove {
                // Remove event if finished.
                if( _Grammar.IsFinished )
                    throw new InvalidOperationException("Trying to remove reduce event after grammar finish");
                else if( !_Finished )
                    throw new InvalidOperationException("Trying to remove event when not finished");
                else if( value == null )
                    throw new ArgumentNullException("Illegal reduce event to remove, is NULL");
                _ReduceEvent -= value;
            }
        }

        /// <summary>
        /// Store the current production to an Xml structure which is initialized by caller.
        /// </summary>
        /// <param name="doc">Document to store the production in.</param>
        /// <param name="xmlprod">Node to attach the current production to.</param>
        internal void StoreXML(XmlDocument doc, XmlNode xmlprod) {
            // Attach possible production specific attribtues.
            if( _RulePrecedence.HasValue )
                xmlprod.Attributes.Append(doc.CreateAttribute("precedence")).InnerText = _RulePrecedence.Value.ToString(CultureInfo.InvariantCulture);
            if( _MergePrecedence.HasValue )
                xmlprod.Attributes.Append(doc.CreateAttribute("mergeprecedence")).InnerText = _MergePrecedence.Value.ToString(CultureInfo.InvariantCulture);

            // Attach symbols.
            foreach( Symbol symb in _Symbols ) {
                // Create new inner node for contained symbol.
                XmlNode xmlsymb = xmlprod.AppendChild(doc.CreateElement("symbol"));
                xmlsymb.Attributes.Append(doc.CreateAttribute("name")).InnerText = symb.Name;
            }
        }

        /// <summary>
        /// Serialize the current production as C# code to the stream writer.
        /// </summary>
        /// <param name="os">Writer to serialize to.</param>
        internal void StoreCS(StreamWriter os) {
            // Write out creation.
            os.Write("new StoredProduction({0}, new List<StoredSymbol>() {{ ", _RulePrecedence.HasValue ? _RulePrecedence.Value.ToString(CultureInfo.InvariantCulture) : "null");
            for( int i = 0; i < _Symbols.Count; ++i )
                os.Write("{0}symbs[\"{1}\"]", i > 0 ? ", " : "", _Symbols[i].Name);
            os.Write(" })");
        }

        /// <summary>
        /// Check the current production against the passed XML representation of a production. In case the production matches
        /// the specified xml serialization, returns true.
        /// </summary>
        /// <param name="xmlprod">XML representation of the production.</param>
        /// <param name="symbids">Symbol ID mapping.</param>
        /// <returns>true iff the XML representation matches this production.</returns>
        internal bool CheckXML(XmlNode xmlprod, Dictionary<string, Symbol> symbids) {
            // Check attributes.
            bool ruleprec = false;
            foreach( XmlAttribute attr in xmlprod.Attributes ) {
                // Switch on attribute name.
                if( attr.Name == "precedence" ) {
                    // Check rule precedence.
                    if( !_RulePrecedence.HasValue || _RulePrecedence.Value != Convert.ToInt32(attr.InnerText, CultureInfo.InvariantCulture) )
                        return false;
                    ruleprec = true;
                }
            }

            // Check whether all attributes matched.
            if( !ruleprec && _RulePrecedence.HasValue )
                return false;

            // Check rule content.
            int i = 0;
            foreach( XmlNode xmlsymb in xmlprod.SelectNodes("symbol") ) {
                // Match symbol. If matched, go to next in chain.
                if( i >= _Symbols.Count || symbids[xmlsymb.Attributes["name"].InnerText] != _Symbols[i] )
                    return false;
                ++i;
            }

            // Check whether full chain matched.
            return i == _Symbols.Count;
        }

        /// <summary>
        /// Check stored production object against this production.
        /// </summary>
        /// <param name="storprod">Stored production object.</param>
        /// <returns>Boolean indicating match of production against stored production.</returns>
        internal bool CheckCS(StoredProduction storprod) {
            // Check precedence.
            if( ( storprod.Precedence.HasValue && !_RulePrecedence.HasValue ) ||
                ( !storprod.Precedence.HasValue && _RulePrecedence.HasValue ) ||
                ( storprod.Precedence.HasValue && _RulePrecedence.HasValue && storprod.Precedence.Value != _RulePrecedence.Value ) )
                return false;

            // Check symbol count and match symbols.
            if( _Symbols.Count != storprod.Symbols.Count )
                return false;
            for( int i = 0; i < _Symbols.Count; ++i )
                if( _Symbols[i].Name != storprod.Symbols[i].Name )
                    // Symbol name doesn't match; production doesn't match.
                    return false;

            // Production matches.
            return true;
        }

        /// <summary>
        /// Fetch the respective symbol at position idx in this production. Symbols present in a production may only be
        /// accessed after the production is finished.
        /// </summary>
        /// <param name="idx">Index of the symbol to access.</param>
        /// <returns>The symbol at the respective position.</returns>
        public Symbol this[int idx] {
            get {
                // Return symbol at index.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to access rule content before finish");
                else if( idx < 0 || _Symbols.Count <= idx )
                    throw new ArgumentOutOfRangeException("Invalid production index requested");
                return _Symbols[idx];
            }
        }

        /// <summary>
        /// Return the number of symbols in the current production (i.e., the production length).
        /// </summary>
        public int Count {
            get {
                // Return symbol count.
                if( !_Finished )
                    throw new InvalidOperationException("Trying to access rule content before finish");
                return _Symbols.Count;
            }
        }

        /// <summary>
        /// Helper to fetch the "tail" of a production, skipping the elements up to and including idx.
        /// </summary>
        /// <param name="idx">The index of the last element to skip.</param>
        /// <returns>Enumerator over the tailing elements.</returns>
        internal IEnumerable<Symbol> Tail(int idx) {
            // Skip idx items from front.
            return _Symbols.Skip<Symbol>(idx + 1);
        }

        /// <summary>
        /// Return a typed enumerator over the symbols contained in this production. The list of symbols may only be accessed
        /// after the production has been finished (i.e., added to a non-terminal).
        /// </summary>
        /// <returns>Enumerator object which lists symbols in this production.</returns>
        public IEnumerator<Symbol> GetEnumerator() {
            // Fetch symbol enumerator.
            if( !_Finished )
                throw new InvalidOperationException("Trying to access rule content before finish");
            return _Symbols.GetEnumerator();
        }

        /// <summary>
        /// Return an untyped enumerator over the symbols contained in this production. The list of symbols may only be accessed
        /// after the production has been finished (i.e., added to a non-terminal).
        /// </summary>
        /// <returns>Enumerator object which lists symbols in this production.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            // Fetch symbol enumerator.
            if( !_Finished )
                throw new InvalidOperationException("Trying to access rule content before finish");
            return _Symbols.GetEnumerator();
        }

        /// <summary>
        /// Create a short string describing the symbols contained in the production.
        /// </summary>
        /// <returns>String description of production.</returns>
        public override string ToString() {
            // Attach all symbols contained.
            StringBuilder rv = new StringBuilder("[");
            foreach( Symbol symb in _Symbols )
                rv.Append(symb);
            rv.AppendFormat(":{0}]", _Tag);

            // Return string form.
            return rv.ToString();
        }

        /// <summary>
        /// Set up the finished flag for this production, signalling that it has been added to a non-terminal.
        /// </summary>
        internal void Finish() {
            // Set finished flag.
            _Finished = true;
        }

        /// <summary>
        /// Create a new production which is the concatenation of a production and a symbol. The returned production is
        /// independent of the original production. Productions may only be added before they are finished (i.e., added to a
        /// non-terminal).
        /// </summary>
        /// <param name="prod">Production to copy.</param>
        /// <param name="symb">Symbol to attach to copy of production.</param>
        /// <returns>New production which contains the concatenation of the production and symbol.</returns>
        public static Production operator +(Production prod, Symbol symb) {
            // Check whether grammars match.
            if( prod == null || symb == null )
                throw new ArgumentNullException("Trying to add null production or symbol as production");
            else if( prod._Grammar != symb.Grammar )
                throw new ArgumentException("Trying to add symbol to production of different grammar");
            else if( prod._Finished )
                throw new InvalidOperationException("Trying to add symbol to finished production");

            // Check whether this production only consists of epsilon. If so, just return copy of joined production.
            if( prod._Symbols.Count == 0 )
                return new Production(symb);

            // Production is non-empty, copy it and add symbol.
            Production copy = new Production(prod);
            copy._Symbols.Add(symb);
            return copy;
        }

        /// <summary>
        /// Create a new production which is the concatenation of the two productions passed. The returned production is
        /// independent of the original production. Productions may only be added before they are finished (i.e., added to a
        /// non-terminal).
        /// </summary>
        /// <param name="prod1">Production to copy.</param>
        /// <param name="prod2">Production to attach to copy of production.</param>
        /// <returns>New production which contains the concatenation of the two productions.</returns>
        public static Production operator +(Production prod1, Production prod2) {
            // Check whether grammars match.
            if( prod1 == null || prod2 == null )
                throw new ArgumentNullException("Trying to add null productions as production");
            else if( prod1._Grammar != prod2._Grammar )
                throw new ArgumentException("Trying to add productions of different grammars");
            else if( prod1._Finished || prod2._Finished )
                throw new InvalidOperationException("Trying to add symbols to finished production");

            // Check whether this production only consists of epsilon. If so, just return a copy of the joined production.
            if( prod1._Symbols.Count == 0 )
                return new Production(prod2);

            // Production is non-empty, copy it and add second production.
            Production copy = new Production(prod1);
            copy._Symbols.AddRange(prod2._Symbols);
            return copy;
        }

        /// <summary>
        /// Execute the reduce event bound to this production. In case no reduce event is defined, return symbols[0].Data, or
        /// null in case the production is empty.
        /// </summary>
        /// <param name="parser">Parser that is executing the reduction.</param>
        /// <param name="symb">Symbol that is being reduced to.</param>
        /// <param name="symbols">List of tokens (symbols carrying data) that are being reduced.</param>
        /// <returns>Value for the reduced token.</returns>
        internal object Execute(Parser parser, Symbol symb, Token[] symbols) {
            // Check event and if set up, call it (to produce result).
            if( _ReduceEvent != null )
                return _ReduceEvent(new ParseState(_Grammar, parser, symb, this), symbols);

            // No event present; use either first symbol or null in case no symbols are present.
            return symbols.Length > 0 ? symbols[0].Data : null;
        }

        /// <summary>
        /// Create a new reduction event helper which returns the value of the token at the specified index.
        /// </summary>
        /// <param name="idx">Index of token to return data for.</param>
        /// <returns>Callback delegate which implements the desired functionality.</returns>
        public static ReduceEventType Fetch(int idx) {
            // Create new delegate which creates a simple rule to return existing token at rule index.
            if( idx < 0 )
                throw new ArgumentOutOfRangeException("Illegal index in resulting production to access");
            return delegate(ParseState state, Token[] symbols) { return symbols[idx].Data; };
        }

        /// <summary>
        /// Create a new reduction helper which returns a constant value regardless of state.
        /// </summary>
        /// <param name="val">Value to return.</param>
        /// <returns>Callback delegate which returns the specified value.</returns>
        public static ReduceEventType Return(object val) {
            // Create new delegate which returns the specified value regardless of parse state.
            return delegate(ParseState state, Token[] symbols) { return val; };
        }

        /// <summary>
        /// Create a new reduction event helper which fails this reduction path.
        /// </summary>
        /// <returns>Callback delegate which implements the desired functionality.</returns>
        public static ReduceEventType FailReduction() {
            // Return delegate that throws event for failure.
            return delegate(ParseState state, Token[] symbols) { throw new FailReductionException(); };
        }

    }

    /// <summary>
    /// Helper class to encapsulate the parser state on a reduction possibility.
    /// </summary>
    public sealed class ParseState {

        // Data.
        private Grammar _Grammar;
        private Parser _Parser;
        private Symbol _Symbol;
        private Production _Production;

        /// <summary>
        /// Initialize a new parser state object which carries information on the current state of the parser on a reduction.
        /// </summary>
        /// <param name="gram">Grammar that is being executed.</param>
        /// <param name="parser">Parser that is executing the reduction.</param>
        /// <param name="symb">Symbol that is being reduced to.</param>
        /// <param name="prod">Production that is being reduced.</param>
        internal ParseState(Grammar gram, Parser parser, Symbol symb, Production prod) {
            // Store data.
            _Grammar = gram;
            _Parser = parser;
            _Symbol = symb;
            _Production = prod;
        }

        /// <summary>
        /// Access the grammar that is being executed on reduction.
        /// </summary>
        public Grammar Grammar {
            get {
                // Return grammar.
                return _Grammar;
            }
        }

        /// <summary>
        /// Access the parser that is executing the reduction.
        /// </summary>
        public Parser Parser {
            get {
                // Return parser.
                return _Parser;
            }
        }

        /// <summary>
        /// Access the symbol that is being reduced to.
        /// </summary>
        public Symbol Symbol {
            get {
                // Return symbol.
                return _Symbol;
            }
        }

        /// <summary>
        /// Access the production that is being reduced.
        /// </summary>
        public Production Production {
            get {
                // Return production.
                return _Production;
            }
        }

    }

}
